package LeetCode;

public class LeetCode209 {

    // https://leetcode.com/problems/minimum-size-subarray-sum/description/

    // 暴力解法
    // 该方法在 Leetcode 中会超时！
    // 时间复杂度: O(n^3)
    // 空间复杂度: O(1)
    public int minSubArrayLen(int s, int[] nums) {

        if (s <= 0 || nums == null)
            throw new IllegalArgumentException("Illigal Arguments");

        int res = nums.length + 1;
        for (int l = 0; l < nums.length; l++)
            for (int r = l; r < nums.length; r++) {
                int sum = 0;
                for (int i = l; i <=r; i++)
                    sum += nums[i];
                if (sum >= s)
                    res = Math.min(res, r - l + 1);
            }

        // 无解的情况
        if (res == nums.length + 1)
            return 0;

        return res;
    }
    // 优化暴力解
    // 时间复杂度: O(n^2)
    // 空间复杂度: O(n)
    public int minSubArrayLen2(int s, int[] nums) {

        if(s <= 0 || nums == null)
            throw new IllegalArgumentException("Illigal Arguments");

        // sums[i]存放nums[0...i-1]的和
        int[] sums = new int[nums.length + 1];
        sums[0] = 0;
        for(int i = 1 ; i <= nums.length ; i ++)
            sums[i] = sums[i-1] + nums[i-1];


        int res = nums.length + 1;
        for(int l = 0 ; l < nums.length ; l ++)
            for(int r = l ; r < nums.length ; r ++){
                // 使用sums[r+1] - sums[l] 快速获得nums[l...r]的和
                if(sums[r+1] - sums[l] >= s)
                    res = Math.min(res, r - l + 1);
            }


        // 无解的情况
        if(res == nums.length + 1)
            return 0;

        return res;
    }
    // 滑动窗口的思路
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    public int minSubArrayLen3(int s, int[] nums) {

        if(s <= 0 || nums == null)
            throw new IllegalArgumentException("Illigal Arguments");

        int l = 0 , r = -1; // nums[l...r]为我们的滑动窗口
        int sum = 0;
        int res = nums.length + 1;

        while(l < nums.length){   // 窗口的左边界在数组范围内,则循环继续
            if(r + 1 < nums.length && sum < s)
                sum += nums[++r];
            else // r已经到头 或者 sum >= s
                sum -= nums[l++];
            if(sum >= s)
                res = Math.min(res, r - l + 1);
        }
        // 无解的情况
        if(res == nums.length + 1)
            return 0;
        return res;
    }

    // 另外一个滑动窗口的实现, 仅供参考
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    public int minSubArrayLen4(int s, int[] nums) {

        if(s <= 0 || nums == null)
            throw new IllegalArgumentException("Illigal Arguments");

        int l = 0 , r = -1; // [l...r]为我们的窗口
        int sum = 0;
        int res = nums.length + 1;

        while(r + 1 < nums.length){   // 窗口的右边界无法继续扩展了, 则循环继续

            while(r + 1 < nums.length && sum < s)
                sum += nums[++r];

            if(sum >= s)
                res = Math.min(res, r - l + 1);

            while(l < nums.length && sum >= s){
                sum -= nums[l++];
                if(sum >= s)
                    res = Math.min(res, r - l + 1);
            }
        }

        if(res == nums.length + 1)
            return 0;
        return res;
    }


    // 时间复杂度: O(nlogn)
    // 空间复杂度: O(n)
    // 二分搜索
    public int minSubArrayLen5(int s, int[] nums) {

        if(s <= 0 || nums == null)
            throw new IllegalArgumentException("Illigal Arguments");

        // sums[i]存放nums[0...i-1]的和
        int[] sums = new int[nums.length + 1];
        sums[0] = 0;
        for(int i = 1 ; i <= nums.length ; i ++)
            sums[i] = sums[i-1] + nums[i-1];

        int res = nums.length + 1;
        for(int l = 0 ; l < nums.length - 1 ; l ++){
            // Java类库中没有内置的lowerBound方法，
            // 我们需要自己实现一个基于二分搜索的lowerBound:)
            int r = lowerBound(sums, sums[l] + s);
            if(r != sums.length){
                res = Math.min(res, r - l);
            }
        }

        if(res == nums.length + 1)
            return 0;
        return res;
    }

    // 在有序数组nums中寻找大于等于target的最小值
    // 如果没有（nums数组中所有值都小于target），则返回nums.length
    private int lowerBound(int[] nums, int target){

        if(nums == null /*|| !isSorted(nums)*/)
            throw new IllegalArgumentException("Illegal argument nums in lowerBound.");

        int l = 0, r = nums.length; // 在nums[l...r)的范围里寻找解
        while(l != r){
            int mid = l + (r - l) / 2;
            if(nums[mid] >= target)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }



    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int s = 7;
        System.out.println((new LeetCode209()).minSubArrayLen(s, nums));
    }
}
